package org.cxy.knapsack;

import java.util.*;

/**
 * 背包问题: 输出价值、选中物品
 *
 * 时间复杂度：O(n × W) - 伪多项式时间
 * 空间复杂度：O(n × W) - 可优化到 O(W)
 * 适用场景：中小规模问题（n × W ≤ 10^6）
 * 优化方向：空间优化、并行计算、近似算法
 */
public class Knapsack01Detailed {

    /**
     * 0-1 背包问题：计算最大价值并返回所选物品
     *
     * @param weights 物品重量数组
     * @param values  物品价值数组
     * @param W       背包最大承重
     * @return        包含最大价值和所选物品索引的 Map
     */
    public static Map<String, Object> knapsackWithItems(int[] weights, int[] values, int W) {
        int n = weights.length; // 物品总数

        // dp[i][w] 表示：从前 i 个物品中选择，背包容量为 w 时能获得的最大价值
        // 多开一行一列，方便处理边界（i=0 或 w=0 的情况）
        int[][] dp = new int[n + 1][W + 1];

        // 填写 dp 表：外层循环遍历物品（从第1个到第n个）
        for (int i = 1; i <= n; i++) {
            int weight = weights[i - 1]; // 当前物品的重量（i-1 是因为数组索引从0开始）
            int value = values[i - 1];  // 当前物品的价值

            // 内层循环遍历背包容量（从 0 到 W）
            for (int w = 0; w <= W; w++) {
                // 默认情况：不选第 i-1 个物品
                // 所以当前最大价值等于“前 i-1 个物品在容量 w 下的最大价值”
                dp[i][w] = dp[i - 1][w];

                // 如果当前背包容量足够装下第 i-1 个物品
                if (w >= weight) {
                    // 尝试选择该物品
                    // 新价值 = 前 i-1 个物品在 (w - weight) 容量下的最大价值 + 当前物品价值
                    int withCurrentItem = dp[i - 1][w - weight] + value;

                    // 取“不选”和“选”的最大值
                    dp[i][w] = Math.max(dp[i][w], withCurrentItem);
                }
            }
        }

        // === 回溯：找出哪些物品被选中 ===
        List<Integer> selectedItems = new ArrayList<>();
        int w = W; // 从最大容量开始回溯

        // 从最后一个物品开始，往前推
        for (int i = n; i >= 1; i--) {
            int weight = weights[i - 1]; // 当前物品重量

            // 如果当前状态的值 != 不选该物品的值，说明选了它
            // 并且要确保容量足够（防止越界）
            if (w >= weight && dp[i][w] != dp[i - 1][w]) {
                selectedItems.add(i - 1); // 记录物品索引（从0开始）
                w -= weight;              // 减去该物品占用的重量，继续向前查找
            }
            // 如果 dp[i][w] == dp[i-1][w]，说明没选这个物品，直接继续
        }

        // 因为是从后往前找的，所以反转列表，使顺序从前往后
        Collections.reverse(selectedItems);

        // 将结果封装返回
        Map<String, Object> result = new HashMap<>();
        result.put("maxValue", dp[n][W]);         // 最大价值
        result.put("selectedItems", selectedItems); // 选中的物品索引列表
        return result;
    }

    // 测试主函数
    public static void main(String[] args) {
        // 示例：5 个物品，展示更复杂的决策过程
        int[] weights = {2, 3, 4, 5, 6}; // 每个物品的重量
        int[] values  = {3, 4, 5, 8, 9};  // 每个物品的价值
        int W = 10;                       // 背包最大承重

        System.out.println("物品信息：");
        System.out.println("索引\t重量\t价值");
        for (int i = 0; i < weights.length; i++) {
            System.out.println(i + "\t" + weights[i] + "\t" + values[i]);
        }
        System.out.println("背包容量: " + W + "\n");

        // 调用算法
        Map<String, Object> result = knapsackWithItems(weights, values, W);
        int maxValue = (int) result.get("maxValue");
        List<Integer> items = (List<Integer>) result.get("selectedItems");

        // 输出结果
        System.out.println("✅ 最大价值: " + maxValue);
        System.out.println("✅ 选中的物品索引: " + items);

        System.out.println("\n📦 选中物品详情:");
        int totalWeight = 0, totalValue = 0;
        for (int index : items) {
            System.out.println("物品 " + index + ": 重量=" + weights[index] + ", 价值=" + values[index]);
            totalWeight += weights[index];
            totalValue += values[index];
        }

        System.out.println("\n✅ 验证:");
        System.out.println("总重量: " + totalWeight + " ≤ " + W + " (未超重)");
        System.out.println("总价值: " + totalValue + " = " + maxValue + " (匹配)");
    }
}